package A1动态规划;

public class LC_1049最后一块石头的重量II {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int stone:stones)
            sum+=stone;
        int target=sum/2;
        int[] dp=new int[target+1];
//        for(int i=0;i<stones.length;i++)
//            for(int j=target;j>=stones[i];j--)
//                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
        for(int stone:stones)
            for(int j=target;j>=stone;j--)
                dp[j]=Math.max(dp[j],dp[j-stone]+stone);
        return sum-dp[target]-dp[target];
    }
}
